package C035;

import java.util.PriorityQueue;

/**
 * ClassName: C05
 * Package: C035
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/8 11:33
 * @Version 1.0
 * @Since 1.0
 */
public class C05 {
    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }
}
class MedianFinder {

    public PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
    public PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

    public MedianFinder() {

    }

    public void addNum(int num) {
        if(maxHeap.isEmpty() || num < maxHeap.peek()) {
            maxHeap.add(num);
        }else {
            minHeap.add(num);
        }

        // 平衡堆
        if(Math.abs(maxHeap.size() - minHeap.size()) > 1) {
            if (maxHeap.size() > minHeap.size()) {
                minHeap.add(maxHeap.poll());
            }else {
                maxHeap.add(minHeap.poll());
            }
        }

    }

    public double findMedian() {
        if (minHeap.size() == maxHeap.size()) {
            return (minHeap.peek() + maxHeap.peek()) / 2D;
        }else {
            return minHeap.size() > maxHeap.size() ? minHeap.peek() : maxHeap.peek();
        }
    }
}
